package org.easy.algorithm.sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @Packge org.easy.algorithm.sort
 * @Autor linNaibin
 * @Description 排序
 * @Version 1.0
 * @Link https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
 * @Date 2021/4/1 10:11
 */
public class Sort {


    // 排序原始数据
  //  private static final int[] NUMBERS = {49, 38, 65, 97, 76, 13, 27, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51};
    private static final int[] NUMBERS = {8,5,2,1};

    /* 冒泡排序 低效 */
    //1.如果元素大小关系不正确，交换这两个数（在本例中为a> b），
    //2.比较一对相邻元素（a，b），
    //3.重复步骤1和2，直到我们到达数组的末尾（最后一对是第（N-2）和（N-1）项，因为我们的数组从零开始）
    //4.到目前为止，最大的元素将在最后的位置。 然后我们将N减少1，并重复步骤1，直到N = 1。
    public static void bubbleSort() {
        int index = NUMBERS.length - 1;
        for (int i = 0; i < index - 1; i++) { //最多做n-1趟排序
            for (int j = 0; j < index - i; j++) {
                if (NUMBERS[j] > NUMBERS[j + 1]) {
                    int temp = NUMBERS[j];
                    NUMBERS[j] = NUMBERS[j + 1];
                    NUMBERS[j + 1] = temp;
                }

            }

        }
        System.out.print("最终排序结果：");
        System.out.println(Arrays.toString(NUMBERS));


    }

    /* 选择排序 */
    // a) 原理：每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。
    // b) 简单选择排序的基本思想：给定数组：int[] arr={里面n个数据}；第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；以此类推，第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。
    public static void selectionSort() {

        int size = NUMBERS.length; //数组长度
        int temp = 0; //中间变量

        for (int i = 0; i < size; i++) {
            //待确定的位置 , 认为是最小的value的下标
            int min = i;
            //选择出应该在第i个位置的数
            for (int j = i + 1; j < size; j++) {
                if (NUMBERS[j] < NUMBERS[min]) {
                    // 记录min的下标
                    min = j;
                }
            }
            //交换两个数
            // i   >>> 第一次被选中的value的下标
            // min >>> 最小value的下标
            temp = NUMBERS[i];
            NUMBERS[i] = NUMBERS[min];
            NUMBERS[min] = temp;
        }
        System.out.print("最终排序结果：");

        System.out.println(Arrays.toString(NUMBERS));


    }


    // 插入排序
    // 1.遍历数组 ， 当前元素 与 前面所有比较，一直找到对的位置再插入。 例如 1，3，5，2（2与5比较-> 互换位置;2与3比较 -> 互换位置；2与1比较-> 位置不变，结束）
    //
    // 2. 如果大，往后移(整体)
    public static void insertSort() {
        // 插入排序，第一个数字不用计算，因为它前面没有数字了，没有对比。
        // 下标从1开始
        for (int i = 1; i < NUMBERS.length; i++) {
            // 当前元素，排序元素 ， 元素被单拎出来 ， 与 i（j）前面的元素比较
            int tmp = NUMBERS[i];
            System.out.println("i 1 >>:" + i);

            // 对比数字的下标（i前一位），tmp 从后往前依次比较
            int j = i - 1; // 此时 i 的前面有 j 个元素
            // 如果 前一位 比 tmp 大
            // 控制j下标，不能为负数。0 >>> 第一个数字
            for (; j >= 0 && tmp < NUMBERS[j]; j--) { // i 的 value 不断与i之前的元素比较，如果i的元素小于j

                // 排序元素: 4
                // before ：[1,2,9,8,4,3,8]
                // ing  :   8 >>> 移动到 4的位置（下标4,替换排序元素4）
                //          9 >>> 移动到 8的位置（下标3）
                //          9之前没有比4更小的了，跳出循环
                NUMBERS[j + 1] = NUMBERS[j]; // 调换位置,数据往后移动（腾出位置给待插入的value）
                // after : [1,2,9,9,8,3,8]
            }
            // 到适合的位置 ，插入 tmp
            // 因为 j-- 的原因， 所以要+1，这个才是正确的下标
            // j 记录的是最小的那个下标，因此 最外层的一次循环只要交换 2个数。
            NUMBERS[j + 1] = tmp;      // 下标 [j + 1]  替换成插入元素
            // after : [1,2,4,9,8,3,8]

        }

        System.out.println(Arrays.toString(NUMBERS));
    }


    // 快速排序
    // array[left] = key
    // 比key小的交换到key左边
    // 比key大的交换到key右边

    // 当 左边指针和右边指针一样时，表示这一轮对比完毕
    public static void quickSort(int[] array, int left, int right) {
        // 1. 递归出口
        if (array == null || array.length == 0 || left > right) {
            return;
        }
        int key = array[left];
        int l = left;
        int r = right;

        // 对比
        while (l != r) {

            // 左边的指针找比key大的
            // 右边的指针找比key小的
            // 当2个条件true
            //  例如  key =3 ，6，key ，2

            // 此时 应该 array[l] 和 array[r] 交换位置

            // 如果 2个指针指向同一个位置，则 arr[l] 和 key 交换位置
            // continue ;

            // 右边 寻找比 key 小的
            while (array[r] >= key && r > l) {
                r--;
            }
            // 左边 寻找比 key 大的
            while (array[l] <= key && l < r) {
                l++;
            }


            // 如果 l、r指向的不是同一个元素
            if (l < r) {
                // swap
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;
            }


        }

        // while l == r 的时候
        array[left] = array[l];
        array[l] = key;

        // 完成了一次交换 ，继续
        System.out.println("=======================================");
        System.out.println("left ::" + left);
        System.out.println("l ::" + l);
        System.out.println("right ::" + right);

        quickSort(array, left, l - 1);
        quickSort(array, l + 1, right);

    }

    public static void main(String[] args) {
        // bubbleSort();
        //selectionSort();
          insertSort();
     //   quickSort(NUMBERS, 0, NUMBERS.length - 1);

        //
        System.out.println(Arrays.toString(NUMBERS));

    }


}
